package com.practice.niuke.new_direct_practice.class23;

/**
 * 判定一个由[a-z]字符构成的字符串和一个包含'.'和'*'通配符的字符串是否匹配。
 * 通配符'.'匹配任意单一字符,'*'匹配任意多个字符包括0个字符。 字符串长度不会超
 * 过100， 字符串不为空。
 * 输入描述:
 * 字符串 str 和包含通配符的字符串 pattern。 1 <= 字符串长度 <= 100输出描述:
 * true 表示匹配， false表示不匹配
 */
public class Code01_RegularExpressionMatch {

    /**
     * 检查函数（检查s和e的有效性）
     *
     * @param s s
     * @param e e
     * @return
     */
	public static boolean isValid(char[] s, char[] e) {
	    // s中不能有'.'和'*'，不然就算违规，直接返回false
		for (int i = 0; i < s.length; i++) {
			if (s[i] == '*' || s[i] == '.') {
				return false;
			}
		}
		// 开头的e[0]位置字符不能是'*'，并且e中不能有相邻的'*'
		for (int i = 0; i < e.length; i++) {
			if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
				return false;
			}
		}
		return true;
	}

    /**
     * 调用递归函数的主函数（TODO: 标记主函数），函数的含义：
     * exp串能否把str串配出来，能就返回true，不能就返回false
     *
     * @param str str
     * @param exp exp
     * @return boolean
     */
	public static boolean isMatch(String str, String exp) {
		if (str == null || exp == null) {
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		return isValid(s, e) ? process(s, e, 0, 0) : false;
	}

    /**
     * 递归函数（潜台词：必须保证ei压中的不是*）：
     * s[si...]能否被e[ei...]匹配
     *
     * @param s
     * @param e
     * @param si
     * @param ei
     * @return
     */
	public static boolean process(char[] s, char[] e, int si, int ei) {
		if (ei == e.length) { // base case   exp已经耗尽了
			return si == s.length;
		}
		// 可能性一：ei+1位置，不是*
		if (
		        // ei+1位置已经是终止位置（ei+1位置已经没有字符了）
		        ei + 1 == e.length
                        ||
                // ei+1位置有字符，但是ei+1位置的字符不是'*'
                 e[ei + 1] != '*'
        ) {
			return si != s.length // si不能耗尽
                    && (e[ei] == s[si] || e[ei] == '.') // si位置字符等于ei位置字符，或者ei位置的字符是'.'
					&& process(s, e, si + 1, ei + 1); // 递归查看process(s, e, si + 1, ei + 1)
		}
		// 可能性二：ei + 1 位置是*
        // 尝试[ei][ei+1]共同的部分，匹配s可能的前缀
		while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
			if (process(s, e, si, ei + 2)) {
				return true;
			}
			si++;
		}
		return process(s, e, si, ei + 2);
	}

    /**
     * 动态规划解法的主函数（TODO: 标记主函数）
     *
     * @param str
     * @param exp
     * @return
     */
	public static boolean isMatchDP(String str, String exp) {
		if (str == null || exp == null) {
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		if (!isValid(s, e)) {
			return false;
		}
		boolean[][] dp = initDPMap(s, e);
		for (int i = s.length - 1; i > -1; i--) {
			for (int j = e.length - 2; j > -1; j--) {
				if (e[j + 1] != '*') {
					dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
				} else {
					int si = i;
					while (si != s.length && (s[si] == e[j] || e[j] == '.')) {
						if (dp[si][j + 2]) {
							dp[i][j] = true;
							break;
						}
						si++;
					}
					if (dp[i][j] != true) {
						dp[i][j] = dp[si][j + 2];
					}
				}
			}
		}
		return dp[0][0];
	}

	public static boolean[][] initDPMap(char[] s, char[] e) {
		int slen = s.length;
		int elen = e.length;
		boolean[][] dp = new boolean[slen + 1][elen + 1];
		dp[slen][elen] = true;
		for (int j = elen - 2; j > -1; j = j - 2) {
			if (e[j] != '*' && e[j + 1] == '*') {
				dp[slen][j] = true;
			} else {
				break;
			}
		}
		if (slen > 0 && elen > 0) {
			if ((e[elen - 1] == '.' || s[slen - 1] == e[elen - 1])) {
				dp[slen - 1][elen - 1] = true;
			}
		}
		return dp;
	}

	public static void main(String[] args) {
		String str = "abcccdefg";
		String exp = "ab.*d.*e.*";
		System.out.println(isMatch(str, exp));
		System.out.println(isMatchDP(str, exp));

	}

}
